package 滑动窗口;

/**
 * 字节
 * 最小覆盖子串: https://leetcode.cn/problems/minimum-window-substring/description/
 */
public class likou76 {

    public String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        // 数组来模拟哈希表。 下标就是字母， 值是次数
        // 统计字符串 t 中字符的频次
        int[] hash1 = new int[128]; 
        int kinds = 0, n = s.length;
        // 统计字符串 t 中字符的频次以及种类
        for(char ch : t) {
            if(hash1[ch] == 0) {
                // 说明是第一次来. 种类加 1
                kinds++;
            }
            hash1[ch]++; // 频次加 1
        }
        int minLen = Integer.MAX_VALUE, begin = -1;
        // 统计窗口中字符的频次. 遍历 s
        int[] hash2 = new int[128];
        for (int left = 0, count = 0, right = 0; right < n; right++) {
            // 1. 进窗口, 同时维护 count 的大小
            char in = s[right];
            hash2[in]++;
            if(hash2[in] == hash1[in]) count++;
            // 2. 判断
            while(count == kinds) {
                // 更新结果
                if(right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    begin = left;
                }
                // 3. 出窗口. 同时维护 count. 必须是 相等的时候count才 - 1. 因为出完窗口之后就不相等了
                char out = s[left++];
                if(hash2[out] == hash1[out]) count--;
                hash2[out]--;
            }
        }
        if(begin == -1) return "";
        else return ss.substring(begin, begin + minLen);
    }

}
